

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.EmptyStackException;
import java.util.Iterator;
import java.util.Stack;

import lombok.extern.slf4j.Slf4j;

/**
 * 使用stack实现四则运算
 * @author zlzhangn
 */
@Slf4j
public class DataStructure_1_stack {
	
	public static double sizeyunsuan(String expresion){
		Stack<String> stack = new Stack<String>();
		Stack<String> postfixExprStack = new Stack<String>();	//后缀表达式栈
		char[] charArr = expresion.toCharArray();
		Stack<String> strArr = new Stack<String>();
		for(int i=0; i<charArr.length; i++){
			if(Character.isDigit(charArr[i])){
				if(strArr.size()>0){
					String prefix = strArr.peek();
					if(!prefix.equals("+")
							&& !prefix.equals("-")
							&& !prefix.equals("*")
							&& !prefix.equals("/")
							&& !prefix.equals("(")
							&& !prefix.equals(")")){
						strArr.push(strArr.pop().concat(Character.toString(charArr[i])));
					}else{
						strArr.push(Character.toString(charArr[i]));
					}
				}else{
					strArr.push(Character.toString(charArr[i]));
				}
			}else{
				strArr.push(Character.toString(charArr[i]));
			}
		}
		//转换为后缀表达式
		for(int i=0; i<strArr.size(); i++){
			String c = strArr.get(i);
			if(!c.equals("+")
					&& !c.equals("-")
					&& !c.equals("*")
					&& !c.equals("/")
					&& !c.equals("(")
					&& !c.equals(")")){
				log.info("数字{}直接输出",c);
				postfixExprStack.push(c);	//数字直接输出
			}else{
				if(c.equals("(")){
					log.info("左括号直接入栈",c);
					stack.push(c);
				}else{
					try {
						if(c.equals(")")){
							log.info("匹配到)，依次出栈直到遇到（停止",c);
							while(stack.size()>-1){
								String topChar = stack.pop();
								if(topChar.equals("(")){
									log.info("遇到（，结束");
									break;
								}
								log.info("{}出栈",topChar);
								postfixExprStack.push(topChar);
							}
						}else{
							while(stack.size()>-1){
								String topChar = stack.peek();
								log.info("正在对比{}和{}",c,topChar);
								if(calcPriority(c, topChar)){
									log.info("{}比{}优先级大，压入栈",c,topChar);
									stack.push(c);
									break;
								}else{
									log.info("{}比{}优先级小,{}出栈",c,topChar,topChar);
									postfixExprStack.push(stack.pop());
								}
							}
						}
					} catch (EmptyStackException  e) {
						log.info("栈为空：{}入栈",c);
						stack.push(c);
					}
				}
			}
		}
		while(stack.size()>0){
			log.info("输出剩余元素{}",stack.peek());
			postfixExprStack.push(stack.pop());
		}
	/*	Iterator<String> it = postfixExprStack.iterator();
		while(it.hasNext()){
			String cha = it.next();
			System.out.println(cha);
		}*/
		return calc(postfixExprStack);
	}
	
	private static double calc(Stack<String> charStack){
		Stack<BigDecimal> resultStack = new Stack<BigDecimal>();
		for(Iterator<String> it = charStack.iterator();it.hasNext();){
			String e = it.next();
			if(!e.equals("+")
					&& !e.equals("-")
					&& !e.equals("*")
					&& !e.equals("/")
					&& !e.equals("(")
					&& !e.equals(")")){
				resultStack.push(new BigDecimal(e.toString()));
			}else{
				BigDecimal b = resultStack.pop();
				BigDecimal a = resultStack.pop();
				BigDecimal result = null;
				char key = e.charAt(0);
				switch(key){
					case '+':
						result = a.add(b);
						log.info("{}+{}={}",a,b,result);
						break;
					case '-':
						result = a.subtract(b);
						log.info("{}-{}={}",a,b,result);
						break;
					case '*':
						result = a.multiply(b);
						log.info("{}*{}={}",a,b,result);
						break;
					case '/':
						result = a.divide(b,2,RoundingMode.HALF_UP);
						log.info("{}/{}={}",a,b,result);
						break;
				}
				resultStack.push(result);
			}
		}
		return resultStack.pop().doubleValue();
	}
	
	private static boolean calcPriority(String a,String b){
		String plus = "+";
		String minus = "-";
		String multiply = "*";
		String divide = "/";
		String left = "(";
		int first = 1;
		int second = 1;
		if(a.equals(multiply) || a.equals(divide)){
			
		}else{
			first = 0;
		}
		if(b.equals(plus) || b.equals(minus)){
			second = 0;
		}else if(b.equals(left)){
			second = -1;
		}
		return first>second;
	}
	
	public static void main(String[] args) throws Exception{
		double result = sizeyunsuan("2*2+(3+1)*123/12*(1/4+1/1*123*(13/12+1))+2/1");
		System.out.println(result);
	}
}
